/*
 * @Author: your name
 * @Date: 2021-03-09 02:22:57
 * @LastEditTime: 2021-03-09 02:22:58
 * @LastEditors: Please set LastEditors
 * @Description: In User Settings Edit
 * @FilePath: /gitee/cpp/library/tree/tree.cpp
 */
#include <stdio.h>

struct Node{
    int val;
    struct Node* left;
    struct Node* right;
};
// test
// 构建二叉树（按前序遍历构建）
struct Node* _MaketreeFirst(int* s, size_t size,int& pos)
{
    struct Node* root = NULL;
    if (pos < size && s[pos] != '#')
    {
        root = new struct Node();
        root->val = s[pos];
        root->left = _MaketreeFirst(s,size,++pos);
        root->right = _MaketreeFirst(s,size,++pos);
    }
    return root;
}

// 前序遍历输出 
void ShowFirst(struct Node* head)
{
    if (head == NULL)
    {
        printf("%c ", '#');
        return;
    }
    printf("%d ", head->val);
    ShowFirst(head->left);
    ShowFirst(head->right);
}

// 中序遍历输出
void ShowMid(struct Node* head)
{
    if (head == NULL)
    {
        printf("%c ", '#');
        return;
    }
    ShowMid(head->left);
    printf("%d ", head->val);
    ShowMid(head->right);
}

// 后序遍历输出
void ShowLast(struct Node* head)
{
    if (head == NULL)
    {
        printf("%c ", '#');
        return;
    }
    ShowLast(head->left);
    ShowLast(head->right);
    printf("%d ", head->val);
}

int main(int argc, const char** argv) {
    int node0[] = {1, 2, '#',4,'#','#',5,'#',7};
    int pos = 0;
    struct Node* root = _MaketreeFirst(node0, 9, pos);
    ShowFirst(root); printf("\n");
    ShowMid(root); printf("\n");
    ShowLast(root); printf("\n");
    return 0;
}
